<?php
/**
 * <https://y.st./>
 * Copyright © 2018 Alex Yst <mailto:copyright@y.st>
 * 
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see <https://www.gnu.org./licenses/>.
**/

$xhtml = array(
	'<{title}>' => 'Assembly, revisited: some assembly required',
	'<{subtitle}>' => 'Written in <span title="Software Engineering 1">CS 2401</span>, finalised on 2018-01-03',
	'<{copyright year}>' => '2018',
	'takedown' => '2017-11-01',
	'<{body}>' => <<<END
<h2>First program</h2>
<p>
	In the assigned pseudocode, <code>J</code> is assigned a value, but <code>j</code> is decremented.
	I&apos;m assuming that this is a typographical error, and that <code>J</code> and <code>j</code> were meant to refer to the same variable.
	As such, I only used <code>j</code> in my code.
</p>
<blockquote>
<h3>Assembly</h3>
<pre><code>// We can&apos;t write arbitrary values anywhere but the A register. We have
// to write the value 5 to A, then move it to D, then put the memory
// address for the j variable in A, then copy the value from D to M.
// It&apos;s just the only way, unless we want to instead write 1 to M and
// increment it four times.
@5
D=A
@j
M=D

// There are two values we can write directly to D or M. Those are 0
// and 1. As we need a 1 here, we can keep things simpler than when we
// set the value of j to 5.
@i
M=1

// We need to loop back to here. Let&apos;s set a named jump-landing
// address. We&apos;ll name it &quot;for&quot;, as it&apos;s the beginning of our for loop.
(FOR)

// This is the tricky part. We need to compute i-5 and jump based on
// the answer. That means we need the A register set to the value of
// the jump-landing address, but we also need to have the A register
// free, either to enter the value 5 or to hold the address of the i
// variable. As messy as it is, we&apos;re going to need to do this in three
// steps. We&apos;ll compute the value, store it in the D register, set the
// A register to the jump&apos;s landing address, then &quot;compute&quot; the value
// held in the D register as the jump condition. Got all that? Let&apos;s
// go.
// 
// First, we enter the value 5.
@5

// Then we move it to the D register.
D=A

// Next, we enter the address of i for comparison.
@i

// Then, we compute the difference between M and D, and store it in the
// D register.
D=M-D

// If we&apos;re done with the loop, we should jump to the end of the loop.
// Let&apos;s use a named jump-landing address, &quot;ENDFOR&quot;, which we&apos;ll
// remember to set at the end of the loop.
@ENDFOR

// We want to *continue* the loop if i is less than 5. We&apos;re at the
// beginning of the loop already though. That means that we want to
// *not* jump if i is less than 5. We want to *jump* if i is *greater
// than or equal to* five.
D;JGE

// We did all that, and we still haven&apos;t even started the loop&apos;s block
// yet. But now we&apos;re ready to start it.
// 
// We set the value of the A register to j&apos;s address, then increment j.
// That&apos;s all we need to do.
@j
M=M+1

// The loop has ended. We need to jump back to the beginning to test
// the continuation condition. We&apos;ll jump back if we&apos;re done with the
// loop.
// 
// Let&apos;s set the value of the A register to FOR, then jump.
@FOR

// This is the end of the program. We&apos;ll need to jump back to here when
// it&apos;s time to terminate the loop.
(ENDFOR)

// This jump here&apos;s a little strange. If we reached the end of one of
// the loop&apos;s iterations, the A register will be set to FOR, so this
// jump will cause the next iteration to begin. This is the desired
// behaviour.
// 
// However, if we just jumped here from the loop&apos;s conditional
// statement, the value of the A register will instead be set to
// ENDFOR. There&apos;s no way to actually terminate a Hack program without
// shutting the whole machine off. As such, it&apos;s customary to end one&apos;s
// program with a jump that jumps back to itself forever. Since we just
// jumped from the loop&apos;s conditional, the value of the A register is
// already set to have jumps lead back here. No additional effort is
// needed, and we just keep jumping in place. Again, this is the
// desired behaviour. Strange, no?
0;JMP</code></pre>
</blockquote>
<h3>Machine code</h3>
<blockquote>
<pre><code>0000000000000101
1110110000010000
0000000000010000
1110001100001000
0000000000010001
1110111111001000
0000000000000101
1110110000010000
0000000000010001
1111000111010000
0000000000001111
1110001100000011
0000000000010000
1111110111001000
0000000000000110
1110101010000111</code></pre>
</blockquote>
<h2>Second program</h2>
<h3>Assembly</h3>
<blockquote>
<pre><code>// We can&apos;t set the value in a variable&apos;s memory location directly. We
// need to enter the value into the system via the A register, copy the
// value into the D register, set the A register to the variable&apos;s
// memory address, then copy the value from the D register to memory.
@4
D=A
@i
M=D

// We need to compare the value in memory to 5, but again, we can&apos;t
// enter that value except via the A register, which is needed to
// access i&apos;s memory location. Therefore, we need to set the value of A
// to 5, copy the value to D, then set the value of A back to i&apos;s
// memory address.
@5
D=A
@i

// We need a label for the else block, but not the if block. We also
// need to compare these two numbers and base our jump off of the
// comparison, but we can&apos;t directly jump from there, because we need
// both registers for the comparison and we need the A register for the
// jump. We&apos;ll need to make the comparison, store it in the D register,
// set the value of the A register to ELSE, then use the value stored
// in D as the jump condition.
D=M-D
@ELSE

// We need to execute the if block if i is less than 5. That means we
// need to jump if i is *greater than or equal to* 5.
D;JGE

// Again, we can&apos;t enter a value directly into memory. We need to enter
// it into the A register, copy it to the D register, set the A
// register to the value of that memory location&apos;s address, then copy
// the value from the D register to memory.
@3
D=A
@j
M=D

// This ends the if block, so we should jump past the else block. Let&apos;s
// set the A register to the address of the ENDIF label, then jump.
@ENDIF
0;JMP

// This begins the else block.
(ELSE)

// Like in the if branch, we need to jump through the same hoops to set
// the variable, but here, we&apos;re using a different value.
@2
D=A
@j
M=D

// This ends both the conditional statement and the script. Let&apos;s set
// the value of the A register to prepare for jumping, then end the
// program with a jump-in-place.
@ENDIF
(ENDIF)
0;JMP</code></pre>
</blockquote>
<h3>Machine code</h3>
<blockquote>
<pre><code>0000000000000100
1110110000010000
0000000000010000
1110001100001000
0000000000000101
1110110000010000
0000000000010000
1111000111010000
0000000000010000
1110001100000011
0000000000000011
1110110000010000
0000000000010001
1110001100001000
0000000000010101
1110101010000111
0000000000000010
1110110000010000
0000000000010001
1110001100001000
0000000000010101
1110101010000111</code></pre>
</blockquote>
<h2>Third program</h2>
<h3>Assembly</h3>
<blockquote>
<pre><code>// First, we set the value of i to 0.
@i
M=0

// We begin a loop, so let&apos;s set a label to jump back to.
(WHILE)

// We need to load a memory for address in preparation for a jump, but
// we need to jump based on a value in memory at another location. To
// handle this, we copy the value from memory to the D register.
// Additionally, because this is the beginning of a loop, the A
// register will only refer to i&apos;s memory location on the first
// iteration. We need to explicitly set the A register to i&apos;s memory
// location first.
@i
D=M
@ENDWHILE

// We need to execute the contents of the loop if i is equal to zero.
// That means we need to jump if i is *not* equal to zero.
D;JNE

// Right here, we increment the value of j. However, j was never
// initialised! This is not a flaw in my translation of the pseudocode,
// but a flaw in the initial pseudocode itself. Anyway, this terribly
// behaviour can have unexpected results. Because we never set the
// value of j to begin with, we don&apos;t know what value we&apos;re going to
// end up with; we&apos;re simply pulling a value from memory. Most likely,
// the initial value will be zero, but it could also be some other
// number. We just don&apos;t know. This is particularly dangerous because
// of our later jump condition. We check to see whether j *equals* 5.
// If j&apos;s memory location *starts* with a value of 5 or higher, we
// won&apos;t hit the loop-breaking condition until j overflows back to 0,
// then increments up to 5.
@j
M=M+1

// The initial pseudocode properly uses a double equal sign
// (comparison) for the while loop, but used a single equal sign
// (assignment) for the if statement. The behaviour of using an
// assignment operator there is language-dependant. In some languages,
// that&apos;d be an error and prevent compilation. In others, the
// assignment would take place, then the value assigned would be cast
// to boolean and used as the condition. Because it&apos;s pseudocode, it&apos;s
// not written in an actual language and we can&apos;t know what should
// happen. I&apos;m going to assume this was a typographical error, and that
// a comparison operator was intended and not an assignment operator.
// As such, I&apos;ll treat this as a normal comparison.
// 
// Let&apos;s copy j into the D register, load the value 5, compare the two,
// store the result in the D register, load the jump address, and
// potentially jump. Note in particular that the end of the if
// statement is also the end of the while loop. As a result, we don&apos;t
// need a separate jump-landing point to go to the end of the if
// statement; we just need to jump back to the beginning of the while
// loop.
D=M
@5
D=D-M
@WHILE

// The following block needs to be run if j is equal to 5, so we need
// to jump if j is *not* equal to 5.
D;JNE

// Let&apos;s load j&apos;s memory address, copy j to the D register, load i&apos;s
// memory address, and copy j&apos;s value to i.
@j
D=M
@i
M=D

// We need to jump back the the beginning of the loop now. Let&apos;s load
// the address for the beginning of the loop, then unconditionally
// jump.
@WHILE

// This is the end of the program, so we should set up the usual
// jump-in-place. To get to this point in the program, we have to jump
// here, so the A register is already set to this point&apos;s address.
// There is no need to set it again. If we reached this point from just
// above, the address for the beginning of the loop will be loaded in
// the A register, so we&apos;ll jump to the beginning of the loop. On the
// other hand, if we jumped here from the beginning of the loop, this
// instruction&apos;s address will be loaded, and we&apos;ll jump in place,
// effectively terminating the program.
(ENDWHILE)
0;JMP</code></pre>
</blockquote>
<h3>Machine code</h3>
<blockquote>
<pre><code>0000000000010000
1110101010001000
0000000000010000
1111110000010000
0000000000010010
1110001100000101
0000000000010001
1111110111001000
1111110000010000
0000000000000101
1111010011010000
0000000000000010
1110001100000101
0000000000010001
1111110000010000
0000000000010000
1110001100001000
0000000000000010
1110101010000111</code></pre>
</blockquote>
<h2>Fourth program</h2>
<h3>Assembly</h3>
<blockquote>
<pre><code>// Hack assembly doesn&apos;t have arrays. This week, no solution to this
// was proposed in the reading material, but on another week, perhaps
// last week, a flawed solution was provided: Have the array&apos;s memory
// address be just the base address, and add the index to the base
// address to get the memory address of the particular value in the
// array. So why is this solution so flawed? Let&apos;s take a look, shall
// we? The hack assembler has no idea that we&apos;re using this variable to
// refer to a multi-location memory segment. That means that if we use
// the memory address A to refer to A[0]&apos;s memory address, then we
// later use a new variable, i, i and A[1] will have the *same* memory
// address! The two will be bound to the same value, and if one is
// updated, they both will be. Joy. 
// 
// The way I see it, there are a few ways around this. The first is to
// set a label at the beginning of the file, then use that label not
// for jumping, but for accessing data memory. If we do that, A[0] will
// overlap with R0, A[1] will overlap with R1, et cetera. We&apos;ll have up
// to sixteen array slots before we run into problems.
// 
// Another option is to just use R0 directly. Why even create the A
// symbol?
// 
// I don&apos;t like either of these options though, as I feel there&apos;s a
// reason why R0 through R15 are reserved in the first place. The third
// option only works if we know how long the array is from the
// beginning and we set the values in order. However, that&apos;s exactly
// what&apos;s going on in the pseudocode for this problem. That makes it a
// viable solution - this time. What we&apos;re going to do is Assign a
// value to A as usual, and assume this to be A[0], then set the
// remaining values, in order, to dummy variables. We&apos;ll then no longer
// use the dummy variables, but the dummy variables will act as
// placeholders for the memory addresses we need reserved. Then, when
// we go to assign an address for the i variable, i won&apos;t overlap with
// any part of A.
// 
// There&apos;s another small fix I&apos;m going to make as well. The pseudocode
// names the array variable A, but in the assembly code, that&apos;ll look
// an awful lot like the A register. There won&apos;t be any ambiguity, as
// references to the A register and the A variable can only exist in
// mutually-exclusive places, but it might look confusing. Furthermore,
// the convention in Hack assembly is to reserve upper-cased symbols as
// labels and use lower-cased symbols as variables. Therefore, I&apos;ll use
// the a variable, not the A variable.
// 
// a will refer to a[0]. This is expected because a&apos;s address plus 0 is
// itself.
@5
D=A
@a
M=D

// These are the dummy variables, given reasonably-understandable
// names. Remember, these overlap with a[1] through a[5], but that is
// exactly the intent; it allows us to reserve those memory addresses
// so that none of them get assigned to the i variable.
// 
// We&apos;re also going to use a little hack here, just because we know the
// values beforehand and they simply decrement from the previous value.
// We&apos;ll use the D register to store the value we want to assign the
// next array index, and decrement D each time. It&apos;ll save a lot of
// clock cycles. To save even more, we&apos;ll decrement in a bit of an
// unintuitive way; this&apos;ll all work out though.
@a1
M=D-1
D=M-1
@a2
M=D
@a3
M=D-1

// We can skip the decrementing on these last two; 1 and 0 are the two
// values we&apos;re able to assign without entering them first.
@a4
M=1
@a5
M=0

// Alright, we now have all the memory segments we need reserved for
// the array, and the values are in the correct spots. Now when we set
// the i variable, it&apos;ll be assigned a memory location *beyond* the
// array, not *overlapping* the array.
@i
M=0

// Here begins the repeating part of our loop, so let&apos;s set a label.
(FOR)

// We can&apos;t directly compare a variable to the value 5, so we need to
// copy the value of i to the D register, set the value of the A
// register to 5, make the comparison, store the comparison in the D
// register, load the jump address in the A register, then potentially
// jump based on the comparison.
// 
// In previous code segments for this assignment, you saw me reload the
// value of the variable before using it at the beginning of the loop.
// However, this is a special case, and that doesn&apos;t need to be done
// this time. In the typical use case for a for loop, the same variable
// is used before the repeating part of the loop (to set the
// conditional variable), at the beginning of the loop (for the
// comparison) and at the end of the loop (to increment the conditional
// variable). In this code segment, we use this typical case. As a
// result, at both points from which we come to this point, the value
// of the A register is already referring to the memory location of i.
// Therefore, we don&apos;t have to load i&apos;s memory address again. This
// isn&apos;t an optimisation I expect a computerised compiler would make,
// but since we&apos;re compiling by hand, it&apos;s an optimisation that we can
// easily make by hand.
D=M
@5
D=D-A

// We&apos;ll load the address of the end of the loop, then jump if the
// condition is met. Otherwise, we execute the contents of the loop. In
// the for statement, we execute the loop if i is less than or equal to
// 5. That means we jump if i is *greater than* 5.
@ENDFOR
D;JGT

// We need to access the array, be we don&apos;t know what array key we&apos;ll
// use beforehand, as we&apos;re using the value of the ever-changing i
// variable as the key. As such, we must calculate the memory address
// by adding the i to a&apos;s address. We made sure all of the array&apos;s
// memory addresses are consecutive, so this will work. Initially, we
// didn&apos;t use this method to set the values because we couldn&apos;t; we
// needed to reserve the memory addresses, which means we needed to use
// named addresses. This time, we can access the array the proper way
// though. *THIS HAS ALL BEEN ACCOUNTED FOR.*
// 
// We&apos;ll load a&apos;s address into the A register, copy it to the D
// register, load i&apos;s address into the A register, then add D to M and
// store it in the A register. As this computed value represents the
// address of the memory segment we need to access, we can copy the
// value of M to the D register as soon as we&apos;re done, making room for
// the jump-landing address we need to load.
@a
D=A
@i
A=D+M
D=M

// Normally, we need to store the value to compare to then perform
// subtraction, but this is another special case. We&apos;re comparing to
// zero, which is the base case Hack uses for comparisons (not to
// mention that x-0==x and 0-x==-x). All we have to do is jump based on
// the value of the D register, as is. Before we do that, we need to
// load the address of the jump landing. Because of the structure of
// the provided code, the point past the if block is the end of the for
// block. To save two clock cycles, we can jump straight to the
// beginning of the for loop instead of jumping to the end of the if
// block, loading the address of the beginning of the for loop, then
// jumping again right away.
@FOR

// We need to execute the if block if a[i] is equal to 0, which means
// we need to jump if a[i] is *not equal* to 0.
D;JNE

// Hack only has two registers. We needed one of them to store a
// jump-landing address and the other to store the value of a[i],
// because the register needed to access a[i] directly via address is
// the same register that has to hold jump-landing addresses. As a
// result, while we still have the value of a[i] on hand, we don&apos;t have
// the *address* of a[i] on hand any more! We&apos;re going to need to
// recompute it.
// 
// First, we load the memory address of a, and copy it to the D
// register. Next, we load the memory address of i. From there, we can
// add D to M, and store that in the A register.
@a
D=A
@i
A=D+M

// I tried several different things here. We need the value 5 in the D
// register, but we had to use both registers for the above
// computation. We could store the result in D instead of A, then load
// 5 into the A register via an A-command ... except that we then have
// our values transposed. We need the above calculation&apos;s output to
// refer to an address, so it needs to end up in the A register. If
// Hack had a third register, this would be a trivial matter, but it
// doesn&apos;t. If the pseudocode used an extra variable for ease, we could
// likewise pull this off cleanly. Instead, we&apos;re going to have to do
// this in a messy way. There are three ways that I can think of.
// 
// The first way is to assume the value of i and manipulate the code
// accordingly. You and I both know that the only case in which this
// code segment will be run is when i is equal to 5, so we can rework
// the logic to store the value of i in the D register, not the address
// of a. Then the address of a can be stored in the A register, the two
// can be added as before, and the result stored in the A register.
// This will almost magically leave us the value we happen to need, 5,
// in the D register. This would be cheating though; it&apos;d be a huge
// rewrite of the program&apos;s logic. We&apos;d get to the right answer, but
// we&apos;d&apos;ve taken the wrong path to get there.
// 
// The second way would be to use another variable. This time though, I
// think we&apos;d be taking the right path, but getting to the wrong
// solution. The extra value would end up in memory where it doesn&apos;t
// belong.
// 
// We&apos;ll take the third solution instead, but it&apos;s a bit messier than
// the other two options. We&apos;ll just set the D register to 1, then
// increment it four times. That&apos;ll give us a 5 in the D register
// without making hacky assumptions and without storing extra values in
// memory. I&apos;m curious to see how other students resolve this issue and
// I&apos;m curious to know how a computerised compiler would handle this
// situation.
D=1
D=D+1
D=D+1
D=D+1
D=D+1

// Now, we can just set the value of a[i] to the value in the D
// register: 5. Come to think of it, maybe we should&apos;ve skipped setting
// the D register to 5 though incrementing and directly applied that
// logic to the value of M.
M=D

// This is the end of the for loop. Let&apos;s jump back to the beginning.
@FOR

// This is the end of the program, so we&apos;ll put the customary
// jump-in-place. To get here, we have to have already loaded the
// address of this location, so we don&apos;t need to load it again. Let&apos;s
// just set the label we used to jump here, then unconditionally jump.
(ENDFOR)

// This jump serves both as the end of the loop and as the end of the
// program. If we jumped here from the beginning of the loop, the
// address in memory will be for this instruction, so we&apos;ll just jump
// in place, effectively terminating the program. Otherwise, we&apos;ve
// gotten here by reaching the end of the for loop (or more precisely,
// the end of the if block nested within the for loop), so the memory
// address for the beginning of the loop is loaded. Either way, this
// jump will take us where we need to go.
0;JMP</code></pre>
</blockquote>
<h3>Machine code</h3>
<blockquote>
<pre><code>0000000000000101
1110110000010000
0000000000010000
1110001100001000
0000000000010001
1110001110001000
1111110010010000
0000000000010010
1110001100001000
0000000000010011
1110001110001000
0000000000010100
1110111111001000
0000000000010101
1110101010001000
0000000000010110
1110101010001000
1111110000010000
0000000000000101
1110010011010000
0000000000101000
1110001100000001
0000000000010000
1110110000010000
0000000000010110
1111000010100000
1111110000010000
0000000000010001
1110001100000101
0000000000010000
1110110000010000
0000000000010110
1111000010100000
1110111111010000
1110011111010000
1110011111010000
1110011111010000
1110011111010000
1110001100001000
0000000000010001
1110101010000111</code></pre>
</blockquote>
END
);
